package com.leetcode.stack;

import java.util.HashMap;
import java.util.Stack;

/**
 * @author: ZhouBert
 * @date: 2019/10/11
 * @description: 20. 有效的括号
 * A
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 * <p>
 * 示例 1:
 * 输入: "()"
 * 输出: true
 * <p>
 * 示例 2:
 * 输入: "()[]{}"
 * 输出: true
 * <p>
 * 示例 3:
 * 输入: "(]"
 * 输出: false
 * <p>
 * 示例 4:
 * 输入: "([)]"
 * 输出: false
 * <p>
 * 示例 5:
 * 输入: "{[]}"
 * 输出: true
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class IsValid20 {

	/**
	 * 将元素一次入栈，当与第一个 XX-理解错误
	 * 不同种类括号之间不能交错！--》所以只要比较peek的元素是否匹配待入栈元素即可
	 * 4ms-78.62
	 * @param s
	 * @return
	 */
	public static boolean isValid(String s) {
		if (s == null || s.length() == 0) {
			return true;
		}

		char[] chars = s.toCharArray();
		///用数组写起来太麻烦了，还是用k-v
		///int[] arr = {'(', ')', '[', ']', '{', '}'};
		HashMap<Character,Character> map=new HashMap<>();
		map.put('(', ')');
		map.put('[', ']');
		map.put('{', '}');

		Stack<Character> stack=new Stack<>();
		for (int i = 0; i < chars.length; i++) {
			if (stack.size()==0){
				stack.push(chars[i]);
			}else if (map.get(stack.peek())!=null&&map.get(stack.peek())==chars[i]){
				stack.pop();
			}else {
				stack.push(chars[i]);
			}
		}
		return stack.empty();
	}



	public static void main(String[] args) {

	}
}
